/*
 * @lc app=leetcode.cn id=76 lang=typescript
 *
 * [76] 最小覆盖子串
 */

// @lc code=start

//  思想：双指针
//  双指针指向窗口两端，不断移动右指针进行扩展
//  用map维持需要匹配的字符，形式：[字符：次数]
//  判断右指针是否匹配，匹配则调整map（减少该字符次数），否则移动
//  当当前窗口包含所有应匹配的值时（map所有字符次数减少到0）
//  移动左指针进行收缩，调整map（增加该字符次数）
//  每一次都记录最短的window

//  复杂度：O(n) O(c) c为s和t的字符集合

function minWindow(s: string, t: string): string {
    let res = ''
    let left = 0, right = 0, map = new Map()
    // t放入map: 字符：次数
    for (let i = 0; i < t.length; i++) {
        let c = t[i]
        map.set(c, (map.get(c) ?? 0) + 1)
    }
    // 记录当前表中字符个数
    let charNums = map.size

    // 遍历s
    while (right < s.length) {
        // 获取当前字符
        let c1 = s[right]
        if (map.has(c1)) {
            map.set(c1, map.get(c1) - 1)
            if (map.get(c1) === 0) {
                // 此字符找完
                charNums--
            }
        }
        // 当在s中找到t所有的字母(所有字符都被找完)，进行收缩
        while (charNums === 0) {
            let c2 = s[left], window = s.slice(left, right + 1)
            // 更新最小的结果
            if (!res || window.length < res.length) {
                res = window
            }
            // 收缩
            if (map.has(c2)) {
                map.set(c2, map.get(c2) + 1)
                if (map.get(c2) > 0) {
                    charNums++
                }
            }
            left++
        }
        right++
    }
    return res
};
// @lc code=end

console.log(minWindow('ADOBECODEBANC', 'ABC')) // "BANC"
console.log(minWindow('A', 'A'))    // "A"
console.log(minWindow('A', 'AA'))   // ""
